package leetcode.set_map;

import java.util.TreeSet;

/**
 * 202. 快乐数
 * <p>
 * 编写一个算法来判断一个数 n 是不是快乐数。
 * <p>
 * 「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，
 * 也可能是 无限循环 但始终变不到 1。如果 可以变为  1，那么这个数就是快乐数。
 * <p>
 * 如果 n 是快乐数就返回 True ；不是，则返回 False 。
 * <p>
 * <p>
 * <p>
 * 示例：
 * <p>
 * 输入：19
 * 输出：true
 * 解释：
 * 1^2 + 9^2 = 82
 * 8^2 + 2^2 = 68
 * 6^2 + 8^2 = 100
 * 1^2 + 0^2 + 0^2 = 1
 * <p>
 * 解析： 获取到每一位数然后进行^2+total,  每次查看n是否满足条件；不满足时返回 n==1
 * 循环当n！=1 && 存放的数字不重复时 进行
 * 时间复杂度分析： O(logN) 主要看循环的次数,外圈循环肯定很少，所以主要看内圈求下一个元素的时间复杂度  logN
 */
public class Solution202 {

    public boolean isHappy(int n) {
        TreeSet<Integer> ts = new TreeSet<>();
        while (n != 1 && !ts.contains(n)) {
            ts.add(n);
            //获取元素
            n = getNext(n);

        }
        return n == 1;
    }

    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }
}
